Continued Fractions

CONTINUED
FRACTIONS

"Continued fractions are objectively the best in approximation technology" (Evelyn Lamb).

"The best approximation of irrational numbers" (A. Khinchin).

"Mathematical representations more natural than decimal" (Wikipedia).

Concepto

Continued fractions are a form of recursive specification of the real numbers that allow their structure and internal arithmetic properties to be revealed, constituting an alternative to the use of decimals. For example, the rational number

190476

can be decomposed as follows:

Therefore,

179/42 = 4 + 1/(3 + 1/(1 + 1/(4 + 1/2))) In this example, you can see that a continued fraction can be represented by a sequence of numbers (which are called partial, incomplete, or integer quotients). In the example, the sequence is (4, 3, 1, 4, 2).

If the fraction were less than 1, then the first quotient would be 0. For example, the fraction 42/179 would be represented by the sequence (0, 4, 3, 1, 4, 2) and the continued fraction is:

42/179=1/(4 + 1/(3 + 1/(1 + 1/(4 + 1/2)))) The successive values of the continued fraction that approximate them towards their final value are called "partial continued fractions". In the case of our example they are:

v1 = c1 = 4
v2 = c1 + 1/c2 = 4 + 1/3 = 13/3 = 3.25
v3 = c1 + 1/(c2 + 1/c3) = 4 + 1/(3 + 1/1) = 17/4 = 4.25
v4 = c1 + 1/(c2 + 1/(c3 + 1/c4)) = 4 + 1/(3 + 1/(1 + 1/4)) = 81/19 = 4.2663157894736842105
v5 = c1 + 1/(c2 + 1/(c3 + 1/(c4 + 1/c5))) = 4 + 1/(3 + 1/(1 + 1/(1 + 1/(4 + 1/2))) = 179/42 = 4. 26190476

Structure of partial quotients of a continued fraction

Every rational number can be decomposed into a finite continued fraction, i.e., the process of obtaining the quotients ends after a finite number of steps. This is easily demonstrated by Euclid's algorithm for obtaining the greatest common divisor of two numbers.

Every irrational number decomposes into infinitely many continued fractions.

If the continued fraction corresponding to an irrational number r is periodic, then r is the solution of a second degree equation.

For example, for √2, the quotients are: (1, 2, 2, ...) eq. (1 2☆)

This can be shown by making √2 = 1 + x. Squaring, we obtain

and therefore,

√2 = 1 + 1/(1 + √2) From this last expression it follows that the continued fraction is infinite:

√2 = 1 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + ...)))) And the partial continued fractions are:

1, 3/2, 7/5, 17/12, 41/29, 29/70, 239/169,... Analogously, one has:

Ratios of √3: (1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...) eq. (1 (1 (1 2)↓☆)
Ratios of √5: (2, 4, 4, 4, 4, 4, 4, 4, ...) eq. (2 4☆)
Ratios of √6: (2, 2, 2, 4, 2, 4, 2, 4, 2, 4, ...) eq. (2 (2 4)↓☆)
Ratios of e: (2, 1, 2, 2, 1, 1, 1, 4, 1, 1, 1, 1, 6, 1, 1, 1, 8, 1, 1, 1, 1, 10, 1, 1, ...) eq. (2 1 (1 1 1)↓&dasv;(2*[1...]))

Partial continued fractions are: 2, 5/2, 8/3, 11/4, 19/7, 79/28,...
Quotients of π: (3, 7, 15, 1, 1, 292, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 84, 2, ...).

They follow an apparently random pattern. Partial continued fractions are:

3, 22/7, 333/106, 355/113, 103993/33102, 104384/33215, 208341/66317, 312689/99532, ...
Ratios of Φ (area ratio): (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...) eq. ( 1☆ )

Φ = 1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + ...))))

This is the simplest continued fraction.

Partial continued fractions, where the numbers of the Fibonacci sequence (1, 1, 3, 5, 8, 8, 13, 21, 34, ...) appear, are:

1, 2 , 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, ...

Generalized continued fractions

A generalized continued fraction is one in which the numerators of the fractions and the partial quotients can be any values, real or complex. It has the form

₁

₂

₃

In this case, the representation could be a sequence of subsequences (a_i, b_i). For example:

√3 = 1 + 2/(2 + 2/(2 + 2/(2 + 2/(2 + 2/(2 + 2 + ...))))
Representation: ((1, 2), (2, 2), (2, 2), (2, 2), (2, 2), ...)
π = 3 + 1²/(6 + 3²/(6 + 5²/(6 + 7²/(6 +...))))
Representation: ((3, 12), (6, 32), (6, 52), (6, 72),...)

When the numerators b_i are all 1 and the a_i are natural numbers, we have simple continued fractions. The simplest continued fraction is the golden ratio.

Square roots as continued fractions

The square root of a number r, √r, can be expressed:

It follows that √r can be expressed as a continued fraction in many ways, depending on the value of a. For example:

r	a	√r
2	1	√2 = 1 + 1/(1 + √2)
2	2	√2 = 2 + (−2)/(2 + √2)
2	3	√2 = 3 + (−7)/(3 + √2)
2	4	√2 = 4 + (−14)/(4 + √2)

For the continued fraction to be simple, it must be satisfied that (r − a²) = 1. For r = 2, a must be 1. For r = 5, a must be 2. Etc.

Continued fractions and quadratic equations

From the second degree equation x² + ax = b, we can deduce the recursive expression

That is, the natural solution of a quadratic equation is a continued fraction. For example, in the case a = b = 1, we have the equation x² + x = 1, and the continued fraction represented by the recursive expression

stands for φ = 1/Φ = 0.6180339... (inverse of the golden ratio). The golden ratio Φ is Φ = 1 + φ = 1.6180339...

The partial quotients of a continued fraction are repeated if and only if they represent a quadratic irrational, that is, if it is a solution of a second degree equation with integer quotients. For example, (1, 1, 1, 1, ...) represents the golden ratio and (1, 2, 2, 2, 2, ...) represents √2.

Advantages of using continued fractions versus decimals

For rational numbers they avoid infinite decimal places.
Reveal the internal structure of real numbers.
They constitute a natural decomposition of a real number in two-dimensional form into simpler elements, as opposed to the linear notation of decimals.
They allow to determine the irrationality of a number. If its development as a continued fraction is infinite, then the number is irrational.
They allow to detect patterns in irrational numbers, which do not appear in the linear decimal representation. For example, in the simple continued fraction of the number e a pattern can be seen. And in the generalized continued fraction of can be appreciated a surprising pattern.
They take up less memory (the expression is more compact) and require less computation time.
They allow simpler and more compact approximation of real numbers. For example, if we consider the decimal representation of π = 3.14159 = 314159/100000, this fraction is less accurate than considering only the first 4 partial quotients (3, 7, 15, 1):
They reveal the analogy of the internal structures of inverse numbers. For example, 179/42 and 42/179 differ only in that 42/179 is represented by a sequence with an additional zero and as a continued fraction is represented by only 6 digits: (0, 4, 3, 1, 4, 2). In contrast, the decimal representation of 42/179 is very complex: it has a period of 178 decimal digits.
In general, a real number can be represented by different continued fractions. This is especially true of square roots. For example,

√3 = 1 + 2/(2 + 2/(2 + 2/(2 + 2/(2 + 2/(2 + ...)))) = 1 + 1/(1 + 1/(1 + 1/(2 + 1/(2 + 1/(1 + 1/(2 + ...))))))

Algoritmos

An algorithm (non-recursive) that computes integer quotients of a fraction n1/n2 is as follows:

⟨( quotients(n1 n2) = ( (s = ()) // result sequence to be returned (initially, empty) (m1° = n1) // initial numerator (m2° = n2) // initial denominator ( (mc° = m1÷m2) // quotient (s° = (s↓ mc) // include quotient in result (mr° = m1 − m2*mc) // remainder (mr = 0) → ¡s // if remainder is zero, return result (m1° = m2) // new numerator (m2° = mr) // new denominator )☆ )! )⟩

Example: quotients(179 42) // ev. (4 3 1 4 2)
Inverse algorithm: given the integer quotients of a finite continued fraction (finite sequence of natural numbers), calculate the two components (n1, n2) of the equivalent rational number.

For its development, it is necessary to:
- Start with the last quotient as the initial value of the fraction.
- Calculate the new value of the fraction, which is the sum of the previous quotient plus the inverse of the current value.
For example, for the fraction 179/42, whose sequence is (4, 3, 1, 1, 4, 2):

Cociente Valor
2 v=2
4 v = 4 +1/v = 4 + 1/2 = 9/2
1 v = 1 + 1/v = 1 + 2/9 = 11/9
3 v = 3 + 1/v = 3 + 9/11 = 42/11
4 v = 4 + 1/v = 4 + 11/42 = 179/42

⟨( fraction(quotients) = ( (i° = quotients#) // number of quotients (nc° = quotients) // initial quotient (nr1° = nc) // initial numerator of result (nr2° = 1) // initial denominator of the result ( (i° = i-1) // point to previous quotient (i=0 → ¡(nr1 nr2)) // if end of quotients, return result (n1° = nr1) // new denominator (n2° = nr2) (nc° = quotient) // new quotient (nr1° = nc + n1) // new numerator of the result (nr2 = n2) // new result denominator )★ )! )⟩

Example: fraction(4 3 1 5 11) // ev. (179 42)

Addenda
Euclid's algorithm of the m.c.d. (greatest common divisor) of two numbers

The larger number is divided by the smaller number.
If the division is exact, the m.c.d. is the smaller one.
If the division is not exact, we divide the divisor by the remainder.
We continue in this way (divisor by remainder) until an exact division is obtained. The last divisor is the m.c.d. If the d.c.m. is 1, the numbers are prime to each other (they have no common factor other than unity).

For example, m.c.d. of 114 and 421:

A little history

The history of continued fractions begins with Euclid's algorithm for calculating the m.c.d. of two natural numbers, where the same operations are performed as in a continued fraction.

The first written record comes from Bombelli's treatise on algebra (1572). Bombelli found a procedure for approximating the roots of quadratic equations by continued fractions. Twenty-four years later, the Italian Pietro Antonio Cataldi (1548-1626) expressed square roots by continued fractions and presented the first formal notation for generalized continued fractions.

John Wallis (1616-1703) introduced the term continued fraction.

Englishman William Brounker (1620-1684) developed the continued fraction method for π.

Euler proved that every irrational quadratic equation can be represented by a simple periodic continued fraction. Lagrange proved the opposite: any periodic continued fraction represents a solution of a quadratic equation.

Bibliography

Angelina, Lemmens. Continued Fractions. Lambert Academic Publishing (LAP), 2015.
Hensley, Doug. Continued Fracions. World Scientific Publishing, 2006.
Khinchin, A. Ya. Continued Fractions. Dover Book son Mathematics, 1997.
Korkina, E.I. The simplest 2-dimensional continued fraction. J. Math. Sci., 82 (5), 1996, pp. 3680-3685.
Lamb, Evelyn. Roots of Unity. What’s so Great about Continued Fractions? Scientific American, March, 12015.
Rockett, Andrew M.; Szüsz, Peter. Continued Fractions. World Scientific Press, 1992.

Cociente	Valor
2	v=2
4	v = 4 +1/v = 4 + 1/2 = 9/2
1	v = 1 + 1/v = 1 + 2/9 = 11/9
3	v = 3 + 1/v = 3 + 9/11 = 42/11
4	v = 4 + 1/v = 4 + 11/42 = 179/42